package 二叉树层序遍历.在每个树行中找最大值;

import 二叉树层序遍历.二叉树的右视图.Test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    /*
    给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
     */
    public List<Integer> largestValues(TreeNode root) {
        // 层序遍历

        if(root==null)
            return Collections.emptyList();

        List<Integer> ans = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        TreeNode p, last = root;
        queue.offer(root);
        int levelMax = root.val;
        while (true) {
            p = queue.poll();
            int num = p.val;
            if (levelMax < num)
                levelMax = num;
            if (p.left != null) queue.offer(p.left);
            if (p.right != null) queue.offer(p.right);
            if (last == p) {
                ans.add(levelMax);
                last = queue.peekLast();
                if(!queue.isEmpty())
                    levelMax = last.val;
                else
                    break;
            }
        }
        return ans;
    }
}
